//判断子序列
class Solution {
public:
    bool isSubsequence(string s, string t) 
    {
        //dp[i][j] s的前i个字符和t的前j个字符构成的子序列长度
        int m=s.size();
        int n=t.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        // int res=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(s[i-1]==t[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    // res=max(res,dp[i][j]);
                }
                else
                {
                    // dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 这个写法也可以
                    //但是要匹配删除的肯定是长的字符即删t的
                    // "既然我跟你不一样 那我就不用我的了"
                    dp[i][j]=dp[i][j-1];
                }
            }
        }
        if(dp[m][n]==s.size()) return true;
        else return false;
    }
};
//最大子数组和
class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        int n=nums.size();
        vector<int>dp(n,INT_MIN);
        //dp[i]以nums[i]结尾的最大子数组和
        dp[0]=nums[0];
        int res=dp[0];
        for(int i=1;i<nums.size();i++)
        {
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            res=max(res,dp[i]);
        }
        return res;
    }
};